home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 1636 < prev    next >
Encoding:
Internet Message Format  |  1996-08-06  |  1.5 KB
  1. Path: newsfeed.internetmci.com!xmission!news
  2. From: tknarr@xmission.com  ( Todd Knarr )
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: deque container - how to implement?
  5. Date: 12 Jan 1996 01:06:43 GMT
  6. Organization: Chaos Central
  7. Message-ID: <4d4c73$qmr@news.xmission.com>
  8. References: <4cvepv$5rn@news.xmission.com> <4d1of1$kj7@rap.SanDiegoCA.ATTGIS.COM>
  9. Reply-To: tknarr@xmission.com ( Todd Knarr )
  10. NNTP-Posting-Host: slc5.xmission.com
  11. X-Newsreader: IBM NewsReader/2 v1.2
  12.  
  13. In <4d1of1$kj7@rap.SanDiegoCA.ATTGIS.COM>, jbc@ElSegundoCA.ATTGIS.COM (Jim Chapman) writes:
  14. >In STL, deque<T> is supposed to support random access in constant time, so
  15. >a linked list implemention wouldn't do.  The first poster was closer to
  16. >the mark. 
  17.  
  18. If you want constant-time access, an array is the only way to implement
  19. it. Unfortunately then your insert time can skyrocket unexpectedly when
  20. you have to copy the entire pointer array to a bigger array. It can also
  21. fail completely if you can't allocate the bigger array ( the non-intrusive
  22. linked-list form can also fail like that, it's just less likely because of
  23. the smaller blocks of memory involved ). It's a trade-off between the
  24. operations needed, memory space used, access time and insert time.
  25.  
  26. --
  27. Todd Knarr : tknarr@xmission.com      |  finger for PGP public key
  28.                                       |  Member, USENET Cabal
  29.  
  30. Seriously, I don't want to die just yet.  I don't care how
  31. good-looking they are, I! don't! want! to! die!"
  32.                                         -- Megazone ( UF1 )
  33.  
  34.